//https://leetcode.cn/problems/decode-ways/description/
//解码方法

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0')
            return 0;

        vector<int> dp(s.size() + 1);
        dp[0] = dp[1] = 1;
        for (int i = 2; i < dp.size(); i++)
        {
            if (s[i - 1] == '0')
            {
                if(s[i - 2] == '0' || s[i - 2] > '2')
                    return 0;
                dp[i] = dp[i - 2];
            }
            else if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))
                dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }

        return dp[dp.size() - 1];
    }
};